МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ЗВІТ
З лабораторної роботи №1
з дисципліни “Алгоритми та методі обчислень”
на тему: “Властивості, параметри та характеристики
складності алгоритму”
Варіант 21
1.Завдання:
Скласти програму (C/C++), яка дозволяє провести порівняння трьох алгоритмів
знаходження НСД за характеристикою часової складності для таких вхідних даних:
2.Варіант завдання.
Варіант № 21 N1 = 526 N2 = 521
3. Алгоритм виконання завдання:
/
4. Результат виконання програми:
/
Рис.1. Результат виконання програми
4. Складність алгоритму:
Відношення часу роботи до кількості стрічок коду
1-ша алгоритм: 5563ns – 40 = 139.08
2-га алгоритм: 25ns – 21 = 1.19
3-тя алгоритм: 28ns – 19 = 1.47
Тому можна вважати, що найефективнішим алгоритмом є 2 алгоритм.
5. Висновок:
На даній лабораторній роботі я навчився порівнювати часові характеристики двох алгоритмів, застосованих для вирішення одного завдання.
Код програми:
//to measure time it is better to run with Linux
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N1 526
#define N2 521
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
#define REPEAT_COUNT 1000000
#define REPEATOR(count, code) \
for (unsigned int indexIteration = (count); indexIteration--;){ code; }
#define TWO_VALUES_SELECTOR(variable, firstValue, secondValue) \
(variable) = indexIteration % 2 ? (firstValue) : (secondValue);
double getCurrentTime(){
clock_t time = clock();
if (time != (clock_t)-1) {
return ((double)time / (double)CLOCKS_PER_SEC);
}
return 0.; // else
}
unsigned long long int f1_GCD(unsigned long long int variableN1, unsigned long long int variableN2){
unsigned long long int returnValue = 1;
for(unsigned long long int i = 1, k = MIN(variableN1, variableN2); i <= k; i++){
if(!(variableN1 % i || variableN2 % i)){
returnValue = i;
}
}
return returnValue;
}
unsigned long long int f2_GCD(unsigned long long int a, unsigned long long int b){
for(unsigned long long int aModB;
aModB = a % b,
a = b,
b = aModB;
);
return a;
}
unsigned long long int f3_GCD(unsigned long long int a, unsigned long long int b){
if(!b){
return a;
}
return f3_GCD(b, a % b); // else
}
int main() {
unsigned long long int vN1 = N1, vN2 = N2, a = MAX(vN1, vN2), b = MIN(vN1, vN2),
vN1_ = vN1, vN2_ = vN2, a_ = a, b_ = b,
returnValue;
double startTime, endTime;
// f1_GCD
startTime = getCurrentTime();
REPEATOR(REPEAT_COUNT,
TWO_VALUES_SELECTOR(vN1, 16, vN1_);
TWO_VALUES_SELECTOR(vN2, 4, vN2_);
returnValue = f1_GCD(a, b);
)
endTime = getCurrentTime();
printf("f1_GCD return %d \r\nrun time: %dns\r\n\r\n",
returnValue,
(unsigned int)((endTime - startTime) * (double)(1000000000 / REPEAT_COUNT)));
// f2_GCD
startTime = getCurrentTime();
REPEATOR(REPEAT_COUNT,
TWO_VALUES_SELECTOR(a, 16, a_);
TWO_VALUES_SELECTOR(b, 4, b_);
returnValue = f2_GCD(a, b);
)
endTime = getCurrentTime();
printf("f2_GCD return %d \r\nrun time: %dns\r\n\r\n",
returnValue,
(unsigned int)((endTime - startTime) * (double)(1000000000 / REPEAT_COUNT)));
// f3_GCD
startTime = getCurrentTime();
REPEATOR(REPEAT_COUNT,
TWO_VALUES_SELECTOR(a, 16, a_);
TWO_VALUES_SELECTOR(b, 4, b_);
returnValue = f3_GCD(a, b);
)
endTime = getCurrentTime();
printf("f3_GCD return %d \r\nrun time: %dns\r\n\r\n",
returnValue,
(unsigned int)((endTime - startTime) * (double)(1000000000 / REPEAT_COUNT)));
printf("Press any key to continue . . .");
getchar();
return 0;
}
